package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * 给定一个整型正数数组arr，代表数值不同的纸牌排成一条线
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿
 * 但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明
 * 请返回最后获胜者的分数
 * <p>
 * 分析：
 * 递归尝试函数
 * 动态规划
 * 尝试优化动态规划
 */
@Slf4j
public class Code03_FirstOrSecondWin {

    public static void EarlyOrLate(int[] arr) {
        int first = first(arr, 0, arr.length - 1);
        int second = second(arr, 0, arr.length - 1);
        log.info("earlyOrLate: first = {}, second = {}", first, second);
    }

    /**
     * 先手取数，能够取到的最大总和
     *
     * @param arr 数字
     * @param l   左边界
     * @param r   右边界
     */
    private static int first(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        // 取 l 或者 r
        int left = arr[l] + second(arr, l + 1, r    );
        int right = arr[r] + second(arr,   l,  r - 1);
        return Math.max(left, right);
    }

    /**
     * 后手取数，能够取到的最大总和
     *
     * @param arr 数字
     * @param l   左边界
     * @param r   右边界
     */
    private static int second(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int left = first(arr, l + 1, r    ); // 对手取l
        int right = first(arr,   l,  r - 1);
        return Math.min(left, right); // 对方会让你拿到的是最小的
    }


    public static void EarlyOrLate2(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];
        for (int i = 0; i < n; i++) {
            f[i][i] = arr[i];
            s[i][i] = 0;
        }
        for (int h =1; h < n; h++) { // 抬升高度
            for (int l = 0; l < n-h; l++) {
                f[l][l+h] = Math.max(arr[l] + s[l+1][l+h], arr[l+h] + s[l][l+h-1]);
                s[l][l+h] = Math.min(f[l+1][l+h], f[l][l+h-1]);
            }
        }
        int first = f[0][n-1];
        int second = s[0][n-1];
        log.info("earlyOrLate: first = {}, second = {}", first, second);
    }


    public static void main(String[] args) {
        int[] arr = {12, 4, 43, 6, 22, 32, 3, 14, 3, 52, 35, 45, 21, 56, 33, 31};
        EarlyOrLate(arr); // earlyOrLate: first = 240, second = 172
        EarlyOrLate2(arr);
    }

}
